/*
 * @lc app=leetcode.cn id=30 lang=cpp
 *
 * [30] 串联所有单词的子串
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    unordered_map<string, int> ori, cnt;
    bool check()
    {
        for (const auto &item : cnt)
        {
            if (ori[item.first] != item.second)
                return false;
        }
        return true;
    }
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> ans;

        const int WORD_LEN = words[0].length();
        const int TOTAL_LEN = WORD_LEN * words.size();

        for (int i = 0; i < words.size(); ++i)
        {
            ori[words[i]]++;
        }

        for (int i = 0; i < WORD_LEN; i++)
        {
            int l = i;
            for (; l < TOTAL_LEN; l += WORD_LEN)
            {
                cnt[s.substr(l, WORD_LEN)]++;
            }
            // l == TOTAL_LEN < s.length() ? TOTAL_LEN : ROUNDS_TO_SIZE(s.length(), WORD_LEN)
            // cout << l << endl;
            for (; l < s.length(); l += WORD_LEN)
            {
                if (check())
                {
                    ans.push_back(l - TOTAL_LEN);
                }
                cnt[s.substr(l - TOTAL_LEN, WORD_LEN)]--;
                cnt[s.substr(l, WORD_LEN)]++;
            }

            if (check())
            {
                ans.push_back(l - TOTAL_LEN);
            }
            cnt.clear();
        }

        return ans;
    }
};
// @lc code=end
